package leetcode;

public class LeetCode74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int row = 0, m = matrix.length - 1, n = matrix[0].length - 1;
        if (target > matrix[m][n])
            return false;
        while (target > matrix[row][n]) {
            row++;
        }
        int left = 0, right = n, mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (matrix[row][mid] < target)
                left = mid + 1;
            else if (matrix[row][mid] > target)
                right = mid - 1;
            else if (matrix[row][mid] == target)
                return true;
        }
        return false;
    }
//------------------------------------------------------------------
}
